本场链接:Codeforces Round #662 Div2

闲话

傻逼

A. Rainbow Dash, Fluttershy and Chess Coloring

傻逼题面:两个玩家分别填色.初始是一个$n*m$的棋盘,第一次只能往边缘相邻的位置上填色.两个人的颜色不同,从第二轮开始,每个人可以往之前填过的不同颜色的旁边位置填色.每个回合可以填无限次,问填满整个棋盘最少要几轮游戏.

思路

直接模拟,发现规律是$n/2+1$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		printf("%d\n",n / 2 + 1);
    }
    return 0;
}

B. Applejack and Storages

傻逼题面:一开始有$n$个木板给定他们的长度.之后有$q$个修改操作,每个修改操作要么是增加一个长度为$x$的模板到可选序列里,要么是删掉一个.保证删掉的一定有.对于每个修改,再修改完之后,问是否能用手上的木板做出一个正方形和一个长方形(正方形也算长方形).输出是否.

数据范围:
$1 \leq n \leq 10^5$
$1 \leq q \leq 10^5$

思路

显然直接维护数量,分别算一下满足$2,4,6,8$的个数各有多少个,对于每个数量下不包含.每个修改都单独处理计算出是否会导致数量的变化,最后直接判是否会有足够的板子搞出两个正方形或一个正方形与一个长方形即可.
如果用数组,且空间没开到$2*10^5$会导致FST.傻逼.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;
	map<int,int> tb;
	int cnt8 = 0,cnt4 = 0,cnt2 = 0,cnt6 = 0;
	for(int i = 1;i <= n;++i)
	{
		int x;cin >> x;
		++tb[x];
	}
	for(auto& t : tb)
	{
		int cnt = t.second;
		if(cnt >= 8)	++cnt8;
		else if(cnt >= 6)	++cnt6;
		else if(cnt >= 4)	++cnt4;
		else if(cnt >= 2)	++cnt2;
	}
	int q;cin >> q;
	while(q--)
	{
		char opt;int v;cin >> opt >> v;
		if(opt == '+')	
		{
			++tb[v];
			int x = tb[v];
			if(x == 2)	++cnt2;
			if(x == 4)	--cnt2,++cnt4;
			if(x == 6)	--cnt4,++cnt6;
			if(x == 8)	--cnt6,++cnt8;	
		}
		else if(opt == '-')
		{
			--tb[v];
			int x = tb[v];
			if(x == 7)	--cnt8,++cnt6;
			if(x == 5)	--cnt6,++cnt4;
			if(x == 3)	--cnt4,++cnt2;
			if(x == 1)	--cnt2;
		}
		// cout << cnt2 << " " << cnt4 << " " << cnt8 << endl;
		if(cnt8 >= 1 
		|| (cnt4 >= 1 && cnt2 >= 2) 
		|| cnt4 >= 2 
		|| (cnt6 >= 1 && cnt2 >= 1)
		|| cnt6 >= 2 
		|| (cnt6 >= 1 && cnt4 >= 1))
			cout << "YES\n";
		else cout << "NO\n";
	}
    return 0;
}

C. Pinkie Pie Eats Patty-cakes

傻逼题面:给定一个长度为$n$的序列.将其任意排列.定义整个序列里的距离是所有相邻元素之间的元素个数.问新排列中所有元素对里的最小距离的最大值是多少.
数据范围:
$2 \leq n \leq 10^5$
$1 \leq a_i \leq n$

思路

最小的最大值,显然是一个二分答案的框架.如果当前答案为$x$且整个序列最后得到的排列里最小距离可以达到$x$,则说明比$x$小的答案都满足,比$x$都大的不一定满足,故左指针向前,反之右指针向左.考虑$check(x)$怎么写:显然整个序列距离要拉到最大是和最多的元素有关的,因此可以优先处理数量最多的元素,把他们先排成一行,对于其他的元素,就相当于是往每两个最多的元素之间插入.这个做法就是让最多的元素之间的距离作为答案,如果其他元素可以全放进去,就说明正确,如果不可以,就说明做不到.如果元素不放在两个之间,而是放在其他地方,比如边界的左边,那么就会导致两个最多的元素之间的距离缩小,使答案变坏.所以应该只往最大元素中间放,显然如果最多的元素有$m$个则会产生$m-1$个缝隙,每个缝隙的距离就是当前二分要检查的距离,容易想到条件就是看整个序列够不够用,即$(m-1)*x + 1 \leq n$.如果最多的元素的种类不止一种,显然可以把他们也算进开始划分的边界的元素里去,即把他们当做一个整体考虑,最后的条件就是$(m-1)*x + cnt \leq n$,其中$cnt$是个数最多的元素的种类数.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(int dist,int m,int cnt,int up)
{
	if((ll)dist * (m - 1) + cnt <= up)	return 1;
	return 0;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		map<int,int> tb;
		int n;scanf("%d",&n);
		for(int i = 1;i <= n;++i)
		{
			int x;scanf("%d",&x);
			++tb[x];
		}
		if(tb.size() == 1)	printf("0\n");
		else
		{
			int m = 0;
			for(auto& t : tb)
				m = max(m,t.second);
			int cnt = 0;
			for(auto& t : tb)
				if(m == t.second)
					++cnt;
			int l = cnt,r = n;
			while(l < r)
			{
				int mid = l + r + 1 >> 1;
				if(check(mid,m,cnt,n))	l = mid;
				else r = mid - 1;
			}
			printf("%d\n",l - 1);
		}
    }
    return 0;
}

D. Rarity and New Dress

傻逼题面:在一个矩阵里找出元素都相同的45°旋转的正方形.
数据范围:
$1 \leq n,m \leq 2000$

思路

对于旋转后的图案,可以大概的看成是由两个框子组成的(即把整个菱形二染色,就可以画成一个有中心块的正方形的框架和一个没有的),所以答案就是这样的两个框子组合在一起,就是整个都相同的45°正方形.这一点可以dp来做,即把每个元素都看作是一个菱形的最下方的元素,从左上右上和上两格的地方下拓展而来.最终统计答案即可.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
char g[N][N];
ll f[N][N];
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i)	
    {
    	scanf("%s",g[i] + 1);getchar();
    }
  	for(int i = 1;i <= n;++i)
  	{
  		for(int j = 1;j <= m;++j)
  		{
  			if(i == 1)	f[i][j] = 1;
  			else if(g[i][j] != g[i - 1][j - 1] 
  			|| g[i][j] != g[i - 1][j + 1] 
  			|| g[i][j] != g[i - 2][j])
  				f[i][j] = 1ll;
  			else	f[i][j] = min({f[i - 1][j - 1],
  								   f[i - 1][j + 1],
  								   f[i - 2][j]}) + 1;
  		}
  	}
  	ll res = 0;
  	for(int i = 1;i <= n;++i)
  	{
  		for(int j = 1;j <= m;++j)
  		{
  			if(g[i][j] == g[i - 1][j])
  				res += min(f[i][j],f[i - 1][j] + 1);
  			else ++ res;	
  		}
  	}
  	printf("%lld",res);
    return 0;
}